\chapter{分治法}

\section{分治法}

\subsection{分治法（Divide and Conquer）}

分治策略是将原问题分解为k个子问题，并对k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。\\

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			level distance=2.5cm,
			level 1/.style={sibling distance=6cm},
			level 2/.style={sibling distance=3cm},
			level 3/.style={sibling distance=2cm}
		]
		\node {problem}
		child {
				node {subproblem}
				child {node {compute}}
				child {node {compute}}
			}
		child {
				node {subproblem}
				child {node {compute}}
				child {node {compute}}
			};
	\end{tikzpicture}
	\caption{分治法}
\end{figure}

将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。\\

分治法的适用条件有以下四点：

\begin{enumerate}
	\item 该问题的规模缩小到一定的程度就可以容易地解决。

	\item 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

	\item 利用该问题分解出的子问题的解可以合并为该问题的解。

	\item 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题（如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好）。
\end{enumerate}

人们在大量事件中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。\\

\subsection{二分搜索}

一个装有16个硬币的袋子，16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些，要求找出这个伪造的硬币。只提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。\\

算法思想是将16个硬币等分成A、B两份，将A放仪器的一边，B放另一边，如果A袋轻，则表明伪币在A，解子问题A即可，否则解子问题B。\\

二分搜索每执行一次循环，待搜索数组的大小减少一半，在最坏情况下，循环被执行了$ O(logn) $次，循环体内运算需要$ O(1) $时间。因此，整个算法在最坏情况下的计算时间复杂性为$ O(logn) $。

\newpage

\section{大整数运算}

\subsection{大整数加法}

如果有两个很大的整数，如何求出它们的和？\\

这还不简单？直接用long类型存储，在程序里相加不就行了？\\

C/C++中的int类型能表示的范围是$ -2^{31} \sim 2^{31} - 1 $，unsigned类型能表示的范围是$ 0 \sim 2^{32} - 1 $，所以int和unsigned类型变量都不能保存超过10位的整数。\\

有时需要参与运算的数可能会远远不止10位，例如计算$ 100! $的精确值。即便使用能表示很大数值范围的double变量，但是由于double变量只有64位，精度也不足以表示一个超过100位的整数。我们称这种基本数据类型无法表示的整数为大整数。\\

在小学的时候，老师教我们用列竖式的方式计算两个整数的和。

\begin{table}[H]
	\centering
	\begin{tabular}{cD{.}{.}{3}}
		  & 426709752318 \\
		+ & 95481253129  \\
		\hline
		= & 522191005447
	\end{tabular}
\end{table}

不仅仅是人脑，对于计算机来说同样如此。对于大整数，我们无法一步到位直接算出结果，所以不得不把计算拆解成一个一个子步骤。\\

可是，既然大整数已经超出了long类型的范围，我们如何来存储这样的整数呢？\\

存放大整数最简单的方法就是使用数组，可以用数组的每一个元素存储整数的每一个数位。如果给定大整数的最长位数是n，那么按位计算的时间复杂度是$ O(n) $。\\

\mybox{大整数加法}

\begin{lstlisting}[language=Python]
def big_int_add(num1, num2):
    # pad the shorter number with leading zeros
    if len(num1) > len(num2):
        num2 = num2.zfill(len(num1))
    else:
        num1 = num1.zfill(len(num2))

    result = ""
    carry = 0
    for i in range(len(num1) - 1, -1, -1):
        digit_sum = int(num1[i]) + int(num2[i]) + carry
        carry = digit_sum // 10
        digit = digit_sum % 10
        result = str(digit) + result
    
    if carry > 0:
        result = str(carry) + result
    return result
\end{lstlisting}

这种思路其实还存在一个可优化的地方。我们之前是把大整数按照每一个十进制数位来拆分，比如较大整数的长度有50位，那么需要创建一个51位的数组，数组的每个元素存储其中一位。\\

真的有必要把原整数拆分得那么细吗？显然不需要，只需要拆分到可以被直接计算的程度就够了。int类型的取值范围是$ -2147483648 \sim 2147483647 $，最多有10位整数。为了防止溢出，可以把大整数的每9位作为数组的一个元素，进行加法运算。如此一来，占用空间和运算次数，都被压缩了9倍。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			level distance=2.5cm,
			level 1/.style={sibling distance=2cm}
		]
		\node {50位}
		child {node {9位}}
		child {node {9位}}
		child {node {9位}}
		child {node {9位}}
		child {node {9位}}
		child {node {9位}};
	\end{tikzpicture}
	\caption{大整数加法优化}
\end{figure}

在Java中，工具类BigInteger和BidDecimal的底层实现也是把大整数拆分成数组进行运算，与此处的思路大体类似。\\

\subsection{大整数乘法}

起初对于大整数乘法，认为只要按照大整数相加的思路稍微做一下变形，就可以轻松实现。但是随着深入的学习，才发现事情并没有那么简单。如果沿用大整数加法的思路，通过列竖式求解……

\begin{table}[H]
	\centering
	\begin{tabular}{cD{.}{.}{3}}
		           & 93281         \\
		$ \times $ & 2034          \\
		\hline
		           & 373124        \\
		           & 279843\ \     \\
		           & 000000\ \ \   \\
		           & 186562\ \ \ \ \\
		\hline
		           & 189733554
	\end{tabular}
\end{table}

乘法竖式的计算过程可以大体分为两步：

\begin{enumerate}
	\item 整数B的每一个数位和整数A所有数位依次相乘，得到中间结果。
	\item 所有中间结果相加，得到最终结果。
\end{enumerate}

这样的做法确实可以实现大整数乘法，由于两个大整数的所有数位都需要一一彼此相乘。如果整数A的长度为m，整数B的长度为n，那么时间复杂度就是$ O(m * n) $。如果两个大整数的长度接近，那么时间复杂度也可以写为$ O(n^2) $。\\

那么有没有优化方法，可以让时间复杂度低于$ O(n^2) $呢？\\

利用分治法可以简化问题的规模，可以把大整数按照数位拆分成两部分。

\vspace{-1cm}

\begin{align*}
	\text{整数1} & = \underbrace{81325}_{A}\underbrace{79076}_{B} \\
	\text{整数2} & = \underbrace{9213}_{C}\underbrace{52184}_{D}
\end{align*}

即：

\vspace{-1cm}

\begin{align*}
	\text{整数1} & = A \times 10^5 + B \\
	\text{整数2} & = C \times 10^5 + D
\end{align*}

如果把两个大整数的长度抽象为m和n，那么：

\vspace{-1cm}

\begin{align*}
	\text{整数1} & = A \times 10^{m/2} + B \\
	\text{整数2} & = C \times 10^{n/2} + D
\end{align*}

因此：

\vspace{-1cm}

\begin{align*}
	 & \text{整数1} \times \text{整数2}                                                        \\
	 & = (A \times 10^{m/2} + B) \times (C \times 10^{n/2} + D)                                \\
	 & = AC \times 10^{m+n \over 2} + AD \times 10^{n \over 2} + BC \times 10^{m \over 2} + BD
\end{align*}

如此一来，原本长度为n的大整数的1次乘积，被转化成了长度为$ n / 2 $的大整数的4次乘积。\\

通过递归把大整数不断地对半拆分，一直拆分到可以直接计算为止。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[
			level distance=2cm,
			level 1/.style={sibling distance=8cm},
			level 2/.style={sibling distance=4cm},
			level 3/.style={sibling distance=2cm}
		]
		\node {100位}
		child {
				node {50位}
				child {
						node {25位}
						child {node {12位}}
						child {node {13位}}
					}
				child {
						node {25位}
						child {node {12位}}
						child {node {13位}}
					}
			}
		child {
				node {50位}
				child {
						node {25位}
						child {node {12位}}
						child {node {13位}}
					}
				child {
						node {25位}
						child {node {12位}}
						child {node {13位}}
					}
			};
	\end{tikzpicture}
	\caption{大整数拆分}
\end{figure}

但是先别高兴地太早，这个方法真的提高了效率吗？

\vspace{-0.5cm}

\begin{align*}
	T(n) = \begin{cases}
		O(1)           & n = 1 \\
		4T(n/2) + O(n) & n > 1
	\end{cases}
\end{align*}

求解得到：

\vspace{-0.5cm}

$$
	T(n) = O(n^2)
$$

闹了半天，时间复杂度还是$ O(n^2) $啊，白高兴一场。但是努力的方向并没有白费，这里还是有优化的方法的。\\

在大整数乘法运算中，如果只简单地利用分治法将大整数的位置减半，并不能降低时间复杂度的阶。分治法把两个大整数相乘到的问题转化为四个较小整数相乘，性能的瓶颈仍旧在乘法上。\\

分治算法的时间复杂度方程为$ W(n) = aW(n/b) + f(n) $，其中$ a $为子问题数，$ n / b $为子问题规模，$ f(n) $为划分与合并工作量。当$ a $较大、$ b $较小、$ f(n) $不大时，$ W(n) = \Theta(n^{log_ba}) $。减少$ a $是降低$ W(n) $的阶的一种途径。利用子问题的依赖问题，可以使某些子问题的解通过组合其它子问题的解而得到。\\

那么，怎样才能减少乘法运算的次数呢？哪怕由四次乘法变成三次乘法也好呀。通过对之前的乘法等式做一些调整，可以减少乘法的次数。

\vspace{-1cm}

\begin{align*}
	 & \text{整数1} \times \text{整数2}                                      \\
	 & = (A \times 10^{n/2} + B) \times (C \times 10^{n/2} + D)              \\
	 & = AC \times 10^n + AD \times 10^{n/2} + BC \times 10^{n/2} + BD       \\
	 & = AC \times 10^n + (AD + BC) \times 10^{n/2} + BD                     \\
	 & = AC \times 10^n + (AD - AC - BD + BC + AC + BD) \times 10^{n/2} + BD \\
	 & = AC \times 10^n + ((A - B)(D - C) + AC + BD) \times 10^{n/2} + BD
\end{align*}

这样一来，原本的4次乘法和3次加法，转变成了3次乘法和6次加法。\\

骗人！最后式子里明明包含五次乘法啊！\\

AC出现了两次，BD也出现了两次，这两个乘积分别只需计算一次就行了，所以总共只需要三次乘法。

\vspace{-0.5cm}

\begin{align*}
	T(n) = \begin{cases}
		O(1)           & n = 1 \\
		3T(n/2) + O(n) & n > 1
	\end{cases}
\end{align*}

求解得到：

\vspace{-0.5cm}

$$
	T(n) = O(n^{log_2{3}}) \approx O(n^{1.59})
$$

\newpage

\section{快速幂}

\subsection{快速幂（Fast Exponentiation）}

使用传统算法计算$ x^n $的时间复杂度为$ \Theta(n) $，然而利用快速幂的算法时间复杂度为$ \Theta(logn) $。

\vspace{-0.5cm}

\begin{align*}
	x^n = \begin{cases}
		x^{n/2} * x^{n/2}             & n\text{为偶数} \\
		x^{(n-1)/2} * x^{(n-1)/2} * x & n\text{为奇数}
	\end{cases}
\end{align*}

例如计算$ 2^{18} $只需要4步即可：

\vspace{-1cm}

\begin{align*}
	2^{18} & = 2^9 * 2^9     \\
	2^9    & = 2^4 * 2^4 * 2 \\
	2^4    & = 2^2 * 2^2     \\
	2^2    & = 2^1 * 2
\end{align*}

\mybox{快速幂}

\begin{lstlisting}[language=Python]
def fast_exponentiation(x, n):
    if n == 0:
        return 1
    
    if n % 2 == 0:
        half = fast_exponentiation(x, n // 2)
        return half * half
    else:
        half = fast_exponentiation(x, (n - 1) // 2)
        return half * half * x
\end{lstlisting}

\newpage

\section{矩阵乘法}

\subsection{矩阵乘法}

假设A和B为n阶矩阵（$ n = 2^k $），计算时，对于C中$ n^2 $个元素，每个元素都需要做n次乘法，因此$ W(n) = O(n^3) $。\\

利用简单的分治策略，可以将矩阵分块计算计算。

\vspace{-0.5cm}

\begin{align*}
	\left( \begin{matrix}
		A_{11} & A_{12} \\
		A_{21} & A_{22}
	\end{matrix} \right)
	\left( \begin{matrix}
		B_{11} & B_{12} \\
		B_{21} & B_{22}
	\end{matrix} \right)
	=
	\left( \begin{matrix}
		C_{11} & C_{12} \\
		C_{21} & C_{22}
	\end{matrix} \right)
\end{align*}

其中，

\vspace{-1cm}

\begin{align*}
	C_{11} = A_{11}B_{11} + A_{12}B_{21} \\
	C_{12} = A_{12}B_{12} + A_{12}B_{22} \\
	C_{21} = A_{21}B_{11} + A_{22}B_{21} \\
	C_{22} = A_{21}B_{12} + A_{21}B_{22}
\end{align*}

这样就把原问题转换为了8个子问题，递推方程为：

\vspace{-0.5cm}

\begin{align*}
	W(n) = \begin{cases}
		1              & n = 1 \\
		8W(n/2) + cn^2 & n > 1
	\end{cases}
\end{align*}

求解得到：

\vspace{-0.5cm}

$$
	W(n) - O(n^3)
$$

简单的分治算法并不能降低时间复杂度的阶，但是矩阵乘法可以通过减少子问题的个数进行优化。\\

\subsection{Strassen矩阵乘法}

让$  M_1,\ M_2,\ \dots,\ M_7 $分别对应矩阵乘法的7个子问题：

\vspace{-0.5cm}

\begin{align*}
	M_1 & = A_{11}(B_{12} - B_{22})            \\
	M_2 & = (A_{11} + A_{12})B_{22}            \\
	M_3 & = (A_{21} + A_{22})B_{11}            \\
	M_4 & = A_{22}(B_{21} - B_{11})            \\
	M_5 & = (A_{11} + A_{22})(B_{11} + B_{22}) \\
	M_6 & = (A_{12} - A_{22})(B_{21} + B_{22}) \\
	M_7 & = (A_{11} - A_{21})(B_{11} + B_{12})
\end{align*}

利用这些中间矩阵，可以得到结果矩阵：

\vspace{-1cm}

\begin{align*}
	C_{11} & = M_5 + M_4 - M_2 + M_6 \\
	C_{12} & = M_1 + M_2             \\
	C_{21} & = M_3 + M_4             \\
	C_{22} & = M_5 + M_1 - M_3 - M_7
\end{align*}

在这些运算中，一共有7个子问题和18次矩阵加减法，时间复杂度为：

\vspace{-1cm}

\begin{align*}
	W(n) = \begin{cases}
		1                   & n = 1 \\
		7W(n/2) + 18(n/2)^2 & n > 1
	\end{cases}
\end{align*}

求解得到：

\vspace{-0.5cm}

$$
	W(n) = O(n^{log7}) \approx O(n^{2.8075})
$$

Coppersmith-Winograd算法是目前已知最好的矩阵乘法算法，时间复杂度为$ O(n^{2.376}) $。矩阵乘法可以应用在科学计算、图形处理、数据挖掘等方面，在回归、聚类、主成分分析、决策树等挖掘算法中常常涉及大规模矩阵运算。

\newpage